#include "stdinc.h"
#include "SearchTree.h"

CSearchTree::CSearchTree()
{
	m_root = CreateItem(NULL, 0);
	m_searchItem = NULL;
}

CSearchTree::~CSearchTree()
{
	DeleteItem(m_root);
	delete m_root;
}

void CSearchTree::Add(char *key, void* value, int flags)
{
	TItem *item = FindItem(key, true);

	item->info.value = value;
	item->info.flags = flags;
}

CSearchTree::TInfo* CSearchTree::Find(char *key)
{
	TItem *item = FindItem(key, false);
	if (item)
		return &item->info;

	return NULL;
}

CSearchTree::TItem* CSearchTree::CreateItem(TItem *parent, char sym)
{
	TItem *item = new TItem;

	for (int i=0; i<SYMBOL_COUNT; i++)
	{
		item->next[i] = NULL;
	}

	item->info.value = NULL;
	item->info.flags = 0;
	item->parent = parent;
	item->parent_sym = sym;

	return item;
}

void CSearchTree::DeleteItem(TItem *item)
{
	for (int i=0; i<SYMBOL_COUNT; i++)
	{
		if (item->next[i])
		{
			DeleteItem(item->next[i]);
			delete item->next[i];
		}
	}
}

int CSearchTree::GetSymbolPos(char c)
{
	if ((c>='a')&&(c<='z'))
		return (c-'a');

	if ((c>='A')&&(c<='Z'))
		return (c-'A');

	if ((c>='0')&&(c<='9'))
		return (c-'0'+26);

	if (c=='_')
		return 36;

	if (c=='+')
		return 37;

	if (c=='-')
		return 38;

	return 39;
}

char CSearchTree::GetSymbolChar(int pos)
{
	char *s = "abcdefghijklmnopqrstuvwxyz0123456789_+-?";

	return s[pos];
}

CSearchTree::TItem* CSearchTree::FindItem(char *key, bool create)
{
	if (!key[0])
		return 0;

	int p = 0;
	TItem *item = m_root;

	while (key[p])
	{
		int s = GetSymbolPos(key[p]);
		if ((item->next[s] == NULL) && create)
		{
			item->next[s] = CreateItem(item, s);
		}

		if (item->next[s])
		{
			item = item->next[s];
			p++;
		}
		else
		{
			return NULL;
		}
	}

	return item;
}

void CSearchTree::GetName(TItem *item, char* name)
{
	int tmp_name[30];
	int tmp_pos = 0;

	while (item->parent)
	{
		tmp_name[tmp_pos++] = GetSymbolChar(item->parent_sym);
		item = item->parent;
	}

	int pos = 0;
	while (tmp_pos)
	{
		name[pos++] = tmp_name[--tmp_pos];
	}

	name[pos] = 0;
}

bool CSearchTree::FindFirst(char *key, char *name)
{
	for (int i=0; i<STACK_DEPTH; i++)
	{
		m_stack[i] = -1;
	}

	m_stackPos = 0;

	m_searchItem = FindItem(key, false);

	name[0] = 0;

	if (!m_searchItem)
		return false;
	
	if (m_searchItem->info.value)
	{
		GetName(m_searchItem, name);
		return true;
	}

	return FindNext(name);
}

bool CSearchTree::FindNext(char *name)
{
	name[0] = 0;

	if (!m_searchItem)
		return false;

	while (1)
	{
		m_stack[m_stackPos]++;
	
		int found = -1;

		while ((m_stack[m_stackPos] < SYMBOL_COUNT)&&(found<0))
		{
			if (m_searchItem->next[m_stack[m_stackPos]])
			{
				found = m_stack[m_stackPos];
			}
			else
			{
				m_stack[m_stackPos]++;
			}
		}

		if (found>=0)
		{
			m_stackPos++;
			m_stack[m_stackPos] = -1;
			m_searchItem = m_searchItem->next[found];

			if (m_searchItem->info.value)
			{
				GetName(m_searchItem, name);
				return true;
			}
		}
		else
		{
			if (m_stackPos == 0)
			{
				m_searchItem = NULL;
				return false;
			}
			else
			{
				m_stackPos--;
				m_searchItem = m_searchItem->parent;
			}
		}
	}


	return false;
}

void CSearchTree::FindValidItem(TItem *item)
{
	for (int i=0; i<SYMBOL_COUNT; i++)
	{
		if (item->next[i])
		{
		}
	}
}